////////////////////////////////////////////////////////////////////////////////
// Copyright (C) 2008 Michiel Helvensteijn                                    //
//                                                                            //
// This file is part of the Mist compiler.                                    //
//                                                                            //
// The Mist compiler is free software: you can redistribute it and/or modify  //
// it under the terms of the GNU General Public License as published by       //
// the Free Software Foundation, either version 3 of the License, or          //
// (at your option) any later version.                                        //
//                                                                            //
// The Mist compiler is distributed in the hope that it will be useful,       //
// but WITHOUT ANY WARRANTY; without even the implied warranty of             //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the              //
// GNU General Public License for more details.                               //
//                                                                            //
// You should have received a copy of the GNU General Public License          //
// along with the Mist compiler.  If not, see <http://www.gnu.org/licenses/>. //
////////////////////////////////////////////////////////////////////////////////

#include "symboltree.hpp"

/******************************************************************************
 * Includes                                                                   *
 ******************************************************************************/

#include <boost/foreach.hpp>
#define foreach BOOST_FOREACH

#include <boost/format.hpp>
using boost::format;

#include <boost/shared_ptr.hpp>
using boost::dynamic_pointer_cast;

#include <typeinfo>

#include <stack>
using std::stack;

#include "common.hpp"
#include "ast/functiontype.hpp"
#include "ast/integertype.hpp"
#include "ast/voidtype.hpp"
#include "visitors/echovisitor.hpp"
#include "parser.hpp"

/******************************************************************************
 * SymbolTree Function Implementations                                        *
 ******************************************************************************/

/*** Path *********************************************************************/

const Path& SymbolTree::path() const {
	return _path;
}

/*** Parent *******************************************************************/

bool SymbolTree::has_parent() {
	return !_parent.expired();
}

shared_ptr<SymbolTree> SymbolTree::parent() {
	assert(has_parent());
	
	return _parent.lock();
}

void SymbolTree::set_parent(shared_ptr<SymbolTree> parent) {
	assert(parent);
	
	_parent = parent;
	_root = parent->root();
	_path = parent->path();
}

/*** Children *****************************************************************/

bool SymbolTree::has_child(const string& name) {
	return (_namedChildren.find(name) != _namedChildren.end());
}

void SymbolTree::insert_child(shared_ptr<SymbolTree> subtree) {
	assert(subtree);
	
	_children.insert(subtree);
	if (typeid(*subtree) == typeid(NamedSymbol)) {
		shared_ptr<NamedSymbol> nsubtree(dynamic_pointer_cast<NamedSymbol>(subtree));
		_namedChildren[nsubtree->name()] = nsubtree;
	}
	
	subtree->set_parent(shared_from_this());
}

shared_ptr<NamedSymbol> SymbolTree::get_child(const string& name) {
	assert(has_child(name));
	
	return _namedChildren.find(name)->second;
}

const set<shared_ptr<SymbolTree> >& SymbolTree::children() {
	return _children;
}

/*** Root *********************************************************************/

shared_ptr<SymbolTree> SymbolTree::root() {
	if (_root.expired())
		return shared_from_this();
	
	return _root.lock();
}

bool SymbolTree::is_root() {
	return (shared_from_this() == root());
}

/*** Path *********************************************************************/

bool SymbolTree::symbol_is_visible(const Path& symbol) {
	stack<shared_ptr<SymbolTree> > seen;
	
	for (shared_ptr<SymbolTree> current = shared_from_this(); true; current = current->parent()) {
		seen.push(current);
		
		if (current->has_child(symbol[0]))
			break;
		
		if (current == root()) {
			if (!symbol.is_absolute())
				return false;
			break;
		}
	}
	
	shared_ptr<NamedSymbol> current;
	for (unsigned i = symbol.is_absolute(); i < symbol.depth(); ++i) {
		bool childFound = false;
		
		do {
			if (seen.top()->has_child(symbol[i])) {
				childFound = true;
				current = seen.top()->get_child(symbol[i]);
			}
			seen.pop();
		} while (!childFound && !seen.empty() && typeid(*seen.top()) == typeid(BlinderSymbol));
		
		if (!childFound)
			return false;
		
		if ((seen.empty() || seen.top() != current) && i < symbol.depth() - 1)
			return false;
	}
	
	return true;
}

shared_ptr<NamedSymbol> SymbolTree::get_visible_symbol(const Path& symbol)  {
	stack<shared_ptr<SymbolTree> > seen;
	
	for (shared_ptr<SymbolTree> current = shared_from_this(); true; current = current->parent()) {
		seen.push(current);
		
		if (current->has_child(symbol[0]))
			break;
		
		if (current == root()) {
			assert(symbol.is_absolute());
				
			break;
		}
	}
	
	shared_ptr<NamedSymbol> current;
	for (unsigned i = symbol.is_absolute(); i < symbol.depth(); ++i) {
		bool childFound = false;
		
		do {
			if (seen.top()->has_child(symbol[i])) {
				childFound = true;
				current = seen.top()->get_child(symbol[i]);
			}
			seen.pop();
		} while (!childFound && !seen.empty() && typeid(*seen.top()) == typeid(BlinderSymbol));
		
		assert(childFound);
		
		assert(!seen.empty() && seen.top() == current || i == symbol.depth() - 1);
	}
	
	return current;
}

shared_ptr<SymbolTree> SymbolTree::containing_function() {
	shared_ptr<SymbolTree> result(shared_from_this());
	
	while (true) {
		if (typeid(*result) == typeid(NamedSymbol)) {
			shared_ptr<NamedSymbol> nresult(dynamic_pointer_cast<NamedSymbol>(result));
			if (typeid(*nresult->type()) == typeid(FunctionType))
				return nresult;
		} else if (result == root()) {
			return result;
		}
		
		result = result->parent();
	}
}

void SymbolTree::insert_used_var(shared_ptr<NamedSymbol> var) {
	_usedVars.insert(var);
}

set<shared_ptr< NamedSymbol> > SymbolTree::used_vars() {
	set<shared_ptr<NamedSymbol> > result;
	foreach (weak_ptr<NamedSymbol> var, _usedVars)
		result.insert(var.lock());
	return result;
}

void SymbolTree::insert_called_function(shared_ptr<NamedSymbol> function) {
	assert(shared_from_this() == root()
	       || typeid(*this) == typeid(NamedSymbol)
	          && typeid(*dynamic_cast<NamedSymbol*>(this)->type()) == typeid(FunctionType));
	assert(typeid(*function->type()) == typeid(FunctionType));
	
	_calledFunctions.insert(function);
}

set<shared_ptr<NamedSymbol> > SymbolTree::called_functions() {
	set<shared_ptr<NamedSymbol> > result;
	foreach (weak_ptr<NamedSymbol> var, _calledFunctions)
		result.insert(var.lock());
	return result;
}

set<shared_ptr<NamedSymbol> > SymbolTree::called_functions_recursive() {
	set<shared_ptr<NamedSymbol> > result = called_functions();
	
	unsigned oldCount;
	do {
		oldCount = result.size();
		
		set<shared_ptr<NamedSymbol> > newSymbols;
		
		foreach (shared_ptr<NamedSymbol> symbol, result)
			foreach (shared_ptr<NamedSymbol> newSymbol, symbol->called_functions())
					newSymbols.insert(newSymbol);
		
		foreach (shared_ptr<NamedSymbol> newSymbol, newSymbols)
			result.insert(newSymbol);
	} while (oldCount < result.size());
	
	return result;
}

set<shared_ptr<NamedSymbol> > SymbolTree::used_vars_recursive() {
	set<shared_ptr<NamedSymbol> > result = used_vars();
	
	foreach (shared_ptr<NamedSymbol> symbol, called_functions_recursive())
		foreach (shared_ptr<NamedSymbol> newSymbol, symbol->used_vars())
			if (!newSymbol->parent()->containing_function()->is_in(shared_from_this()))
				result.insert(newSymbol);
	
	return result;
}

set<shared_ptr<NamedSymbol> > SymbolTree::used_vars_recursive_without_functions() {
	set<shared_ptr<NamedSymbol> > result = used_vars_recursive();
	
	for (set<shared_ptr<NamedSymbol> >::iterator i = result.begin(); i != result.end();) {
		if (typeid(*(*i)->type()) == typeid(FunctionType))
			result.erase(i++);
		else
			++i;
	}
	
	return result;
}

void SymbolTree::insert_written_var(shared_ptr<NamedSymbol> var) {
	_writtenVars.insert(var);
}

set<shared_ptr<NamedSymbol> > SymbolTree::written_vars() {
	set<shared_ptr<NamedSymbol> > result;
	foreach (weak_ptr<NamedSymbol> var, _writtenVars)
		result.insert(var.lock());
	return result;
}

set<shared_ptr<NamedSymbol> > SymbolTree::written_vars_recursive() {
	set<shared_ptr<NamedSymbol> > result = written_vars();
	
	foreach (shared_ptr<NamedSymbol> symbol, called_functions_recursive())
		foreach (shared_ptr<NamedSymbol> newSymbol, symbol->written_vars())
			if (!newSymbol->parent()->containing_function()->is_in(shared_from_this()))
				result.insert(newSymbol);
	
	return result;
}

bool SymbolTree::is_in(shared_ptr<SymbolTree> other) {
	shared_ptr<SymbolTree> current(shared_from_this());
	
	while (true) {
		if (current == other)
			return true;
		
		if (current == root())
			return false;
		
		current = current->parent();
	}
}

ostream& SymbolTree::report_to_stream(ostream& out) {
	// First the named symbols
	map<Path, shared_ptr<SymbolTree> > m;
	foreach (shared_ptr<SymbolTree> child, _children)
		m[child->path()] = child;
	std::pair<Path, shared_ptr<SymbolTree> > p;
	foreach (p, m)
		p.second->report_to_stream(out);
	
	return out;
}

SymbolTree::SymbolTree() {
	unnamedScopeCount = 0;
	_path += "";
}

/******************************************************************************
 * NamedSymbol Function Implementations                                       *
 ******************************************************************************/

NamedSymbol::NamedSymbol(const string& name, const CodeLocation& declarationLocation, shared_ptr<Type> type, AccessType accessType, bool logical) : _name(name), _location(declarationLocation), _type(type), _accessType(accessType), _logical(logical) {
} // intentionally empty

NamedSymbol::NamedSymbol(const string& name, shared_ptr<Type> type, AccessType accessType, bool logical) : _name(name), _type(type), _accessType(accessType), _logical(logical) {
} // intentionally empty

const string& NamedSymbol::name() const {
	return _name;
}

Path NamedSymbol::scope() const {
	return path().tail();
}

void NamedSymbol::set_parent(shared_ptr<SymbolTree> parent) {
	SymbolTree::set_parent(parent);
	_path += name();
}

bool NamedSymbol::has_local_symbol(const string& symbol) {
	assert(!symbol.empty());
	
	stack<shared_ptr<SymbolTree> > S;
	S.push(shared_from_this());
	
	while (!S.empty()) {
		shared_ptr<SymbolTree> current(S.top());
		S.pop();
		
		foreach (shared_ptr<SymbolTree> node, current->children()) {
			if (typeid(*node) == typeid(NamedSymbol)) {
				shared_ptr<NamedSymbol> nnode(dynamic_pointer_cast<NamedSymbol>(node));
				if (nnode->name() == symbol)
					return true;
			} else if (typeid(*node) == typeid(BlinderSymbol)) {
				S.push(node);
			}
		}
	}
	
	return false;
}

shared_ptr<NamedSymbol> NamedSymbol::get_local_symbol(const string& symbol) {
	assert(!symbol.empty());
	
	stack<shared_ptr<SymbolTree> > S;
	S.push(shared_from_this());
	
	while (!S.empty()) {
		shared_ptr<SymbolTree> current(S.top());
		S.pop();
		
		foreach (shared_ptr<SymbolTree> node, current->children()) {
			if (typeid(*node) == typeid(NamedSymbol)) {
				shared_ptr<NamedSymbol> nnode(dynamic_pointer_cast<NamedSymbol>(node));
				if (nnode->name() == symbol)
					return nnode;
			} else if (typeid(*node) == typeid(BlinderSymbol)) {
				S.push(node);
			}
		}
	}
	
	assert(false);
}

bool NamedSymbol::declaration_location_is_set() const {
	return (!_location.begin().file().empty());
}

const CodeLocation& NamedSymbol::declaration_location() const {
	return _location;
}

shared_ptr<Type> NamedSymbol::type() const {
	return _type;
}

AccessType NamedSymbol::access_type() const {
	return _accessType;
}

bool NamedSymbol::logical() const {
	return _logical;
}

ostream& NamedSymbol::report_to_stream(ostream& out) {
	out << format("%1$-25s %2% : %3%\n") % path() % (logical() ? "(l)" : "   ") % echo(type());
	
	return SymbolTree::report_to_stream(out);
}

/******************************************************************************
 * UnnamedSymbol Function Implementations                                     *
 ******************************************************************************/

void UnnamedSymbol::set_parent(shared_ptr<SymbolTree> parent) {
	SymbolTree::set_parent(parent);
	parent->unnamedScopeCount++;
	_path += to_string(parent->unnamedScopeCount);
}

bool UnnamedSymbol::has_local_symbol(const string& symbol) {
	assert(!symbol.empty());
	
	stack<shared_ptr<SymbolTree> > S;
	S.push(shared_from_this());
	
	while (!S.empty()) {
		shared_ptr<SymbolTree> current(S.top());
		S.pop();
		
		foreach (shared_ptr<SymbolTree> node, current->children()) {
			if (typeid(*node) == typeid(NamedSymbol)) {
				shared_ptr<NamedSymbol> nnode(dynamic_pointer_cast<NamedSymbol>(node));
				if (nnode->name() == symbol)
					return true;
			} else if (typeid(*node) == typeid(BlinderSymbol)) {
				S.push(node);
			}
		}
	}
	
	return false;
}

shared_ptr<NamedSymbol> UnnamedSymbol::get_local_symbol(const string& symbol) {
	assert(!symbol.empty());
	
	stack<shared_ptr<SymbolTree> > S;
	S.push(shared_from_this());
	
	while (!S.empty()) {
		shared_ptr<SymbolTree> current(S.top());
		S.pop();
		
		foreach (shared_ptr<SymbolTree> node, current->children()) {
			if (typeid(*node) == typeid(NamedSymbol)) {
				shared_ptr<NamedSymbol> nnode(dynamic_pointer_cast<NamedSymbol>(node));
				if (nnode->name() == symbol)
					return nnode;
			} else if (typeid(*node) == typeid(BlinderSymbol)) {
				S.push(node);
			}
		}
	}
	
	assert(false);
}

void UnnamedSymbol::add_default_symbols() {
	try {
		shared_ptr<NamedSymbol> readSymbol(new NamedSymbol("read", parse<FunctionType>("(int)function()"), AccessType(true, false, true, false)));
		insert_child(readSymbol);
		
		shared_ptr<NamedSymbol> writeSymbol(new NamedSymbol("write", parse<FunctionType>("(void)function(int)"), AccessType(true, false, true, false)));
		insert_child(writeSymbol);
	} catch (ParserException& pe) {
		assert(false);
	}
}

/******************************************************************************
 * BlinderSymbol Function Implementations                                     *
 ******************************************************************************/

bool BlinderSymbol::has_local_symbol(const string& symbol) {
	assert(!symbol.empty());
	
	shared_ptr<SymbolTree> current(shared_from_this());
	
	while (typeid(*current) == typeid(BlinderSymbol))
		current = current->parent();
	
	return current->has_local_symbol(symbol);
}

shared_ptr<NamedSymbol> BlinderSymbol::get_local_symbol(const string& symbol) {
	assert(!symbol.empty());
	
	assert(has_local_symbol(symbol));
	
	shared_ptr<SymbolTree> current(shared_from_this());
	
	while (typeid(*current) == typeid(BlinderSymbol))
		current = current->parent();
	
	return current->get_local_symbol(symbol);
}

/******************************************************************************
 * Output Stream Operator Implementation                                      *
 ******************************************************************************/

symboltable::symboltable(shared_ptr<Node> tree) : _tree(tree) {
} // intentionally empty

symboltable::operator string() const {
	ostringstream sout;
	
	sout << *this;
	
	return sout.str();
}

ostream& symboltable::send_to_stream(ostream& out) const {
	return _tree->scope()->report_to_stream(out);
}
